# -*- coding: utf-8 -*-
# 合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度
# 示例:
# 输入:
# [
#   1->4->5,
#   1->3->4,
#   2->6
# ]
# 输出: 1->1->2->3->4->4->5->6
import sys;
import math;
from Queue import PriorityQueue;

def printList(head):
    current = head;
    v_log = [];
    while current:
        v_log.append(current.val);
        current = current.next;
    print v_log;

def printNodeList(node_list):
    log = "";
    for i in xrange(0, len(node_list)):
        if not node_list[i]:
            continue;
        log += "%d" % node_list[i].val + " ";
    print log;


# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None

# # 时间复杂度n平方的解决方案
# # k个链表总共n个元素，时间复杂度为O(kn)
# # 一遍过但是击败8%的敌人，惨呀!!
# class Solution(object):
#     def mergeKLists(self, lists):
#         """
#         :type lists: List[ListNode]
#         :rtype: ListNode
#         """
#         if len(lists)==0:
#             return None;
#         if len(lists)==1:
#             return lists[0];
#         rtn = lists[0];

#         for i in xrange(1, len(lists)):
#             l1 = rtn;
#             l2 = lists[i];
#             merge = ListNode(-1);
#             current = merge;
#             while l1 and l2:
#                 # print "#";
#                 # printList(merge);
#                 # print [l1.val, l2.val];
#                 if l1.val < l2.val:
#                     current.next = l1;
#                     l1 = l1.next;
#                 else:
#                     current.next = l2;
#                     l2 = l2.next;
#                 current = current.next;
#                 # printList(merge);
#             if l1:
#                 current.next = l1;
#             if l2:
#                 current.next = l2;
#             rtn = merge.next;
#         return rtn;

# # 接近于O(n)
# # 算法复杂度计算错误O(kn)，计算错误的原因是把k看做是有限的常亮，而k可能是和n通量级的存在是不能忽略的
# # 击败18%的用户，纳尼........
# class Solution(object):
#     def mergeKLists(self, lists):
#         """
#         :type lists: List[ListNode]
#         :rtype: ListNode
#         """
#         if len(lists)==0:
#             return None;
#         if len(lists)==1:
#             return lists[0];

#         # 插入排序所有最小节点
#         min_nodes = [ListNode(sys.maxint)];
#         for i in xrange(0, len(lists)):
#             if not lists[i]:
#                 continue;
#             for j in xrange(len(min_nodes)):
#                 if lists[i].val < min_nodes[j].val:
#                     break;
#             min_nodes.insert(j, lists[i]);

#         # 空链表检测 
#         # eg: [[],[]]
#         if len(min_nodes)==1:
#             return None;

#         if len(min_nodes)==2:
#             return min_nodes[0];

#         rtn = ListNode(-1);
#         current = rtn;
#         while len(min_nodes) > 2:
#             if min_nodes[0].val <= min_nodes[1].val:
#                 current.next = min_nodes[0];
#                 current = current.next;
#                 min_nodes[0] = min_nodes[0].next;
#             else:
#                 temp = min_nodes[0];
#                 for i in xrange(1, len(min_nodes)):
#                     if temp.val > min_nodes[i].val:
#                         min_nodes[i - 1] = min_nodes[i];
#                     else:
#                         min_nodes[i - 1] = temp;
#                         break;
#             if not min_nodes[0]:
#                 del min_nodes[0];
#             # printNodeList(min_nodes);

#         current.next = min_nodes[0];
#         return rtn.next;

# # 优化以上的算法
# # 不使用del，排除del的影响
# class Solution(object):
#     def mergeKLists(self, lists):
#         """
#         :type lists: List[ListNode]
#         :rtype: ListNode
#         """
#         if len(lists)==0:
#             return None;
#         if len(lists)==1:
#             return lists[0];

#         # 插入排序所有最小节点
#         min_nodes = [ListNode(sys.maxint)];
#         for i in xrange(0, len(lists)):
#             if not lists[i]:
#                 continue;
#             for j in xrange(len(min_nodes)):
#                 if lists[i].val < min_nodes[j].val:
#                     break;
#             min_nodes.insert(j, lists[i]);

#         # 空链表检测 
#         # eg: [[],[]]
#         if len(min_nodes)==1:
#             return None;

#         if len(min_nodes)==2:
#             return min_nodes[0];

#         rtn = ListNode(-1);
#         current = rtn;
#         index_l = 0;
#         index_r = 1;
#         while index_r < len(min_nodes) - 1:
#             # print "-";
#             # printNodeList(min_nodes);
#             if min_nodes[index_l].val <= min_nodes[index_r].val:
#                 current.next = min_nodes[index_l];
#                 current = current.next;
#                 min_nodes[index_l] = min_nodes[index_l].next;
#             else:
#                 temp = min_nodes[index_l];
#                 temp_index = index_l;
#                 # print "#";
#                 for i in xrange(temp_index + 1, len(min_nodes)):
#                     # printNodeList(min_nodes);
#                     if not (min_nodes[i]):
#                         continue;
#                     if temp.val > min_nodes[i].val:
#                         min_nodes[temp_index] = min_nodes[i];
#                         min_nodes[i] = None;
#                     else:
#                         min_nodes[temp_index] = temp;
#                         break;
#                     temp_index += 1;
#                 for index_r in xrange(index_l + 1, len(min_nodes)):
#                     if min_nodes[index_r]:
#                         break;
#             if min_nodes[index_l]:
#                 continue;
#             index_l = index_r;
#             for index_r in xrange(index_l + 1, len(min_nodes)):
#                 if min_nodes[index_r]:
#                     break;

#         for node in min_nodes:
#             if node:
#                 current.next = node;
#                 break;
#         return rtn.next;

# 接近于n的时间复杂度
# 每一个元素需要对比k次，时间复杂度为kn
# 当链表中每一个链表都只有一个元素时，这个算法会退化为插入排序，时间复杂度变为n平方
class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        if len(lists)==0:
            return None;
        if len(lists)==1:
            return lists[0];

        # 插入排序所有最小节点
        min_nodes = [];
        for i in xrange(0, len(lists)):
            if not lists[i]:
                continue;
            min_nodes.append(lists[i]);
        min_nodes = sorted(min_nodes, key = lambda x : x.val);

        # 空链表检测 
        # eg: [[],[]]
        if len(min_nodes)==0:
            return None;

        if len(min_nodes)==1:
            return min_nodes[0];

        rtn = ListNode(-1);
        current = rtn;
        while len(min_nodes) > 1:
            if min_nodes[0].val <= min_nodes[1].val:
                current.next = min_nodes[0];
                current = current.next;
                min_nodes[0] = min_nodes[0].next;
            else:
                min_nodes = sorted(min_nodes, key = lambda x : x.val);

            if not min_nodes[0]:
                del min_nodes[0];

        current.next = min_nodes[0];
        return rtn.next;




# # 查看评论
# # 为啥我暴力的合并数据到一个数组，然后直接排序的结果是最优的，这都什么鬼
# # why!!!!!!!!!!!!
# # 竟然只用了68毫秒
# # 时间复杂度O(nlg(n))
# class Solution(object):
#     def mergeKLists(self, lists):
#         """
#         :type lists: List[ListNode]
#         :rtype: ListNode
#         """
#         val_list = [];
#         for signal_list in lists:
#             while signal_list:
#                 val_list.append(signal_list.val);
#                 signal_list = signal_list.next;

#         val_list.sort();

#         # 排除排序算法的影响，哪怕使用了插入排序，仍然是比上面第二个方法快了一倍多Why?
#         # temp = val_list;
#         # val_list = [sys.maxint];
#         # for val in temp:
#         #     for i in xrange(0, len(val_list)):
#         #         if val_list[i] < val:
#         #             continue;
#         #         val_list.insert(i, val);
#         #         break;
#         # del val_list[-1];

#         rtn = ListNode(-1);
#         current = rtn;
#         for val in val_list:
#             current.next = ListNode(val);
#             current = current.next;
#         return rtn.next;


# 仔细分析时间复杂度以后，使用两两合并和优先队列的方法应该是时间复杂度最低的算法O(klg(n))
# 以下是2中算法的实现方式
class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        if len(lists)==0:
            return None;
        while len(lists) > 1:
            temp = [];
            for i in xrange(0, len(lists), 2):
                if i == len(lists) - 1:
                    temp.append(lists[i]);
                    break;
                temp.append(self.merge2Lists(lists[i], lists[i + 1]));
            lists = temp;
        return lists[0];

    def merge2Lists(self, list_1, list_2):
        if not list_1: 
            return list_2;
        if not list_2:
            return list_1;
        head = ListNode(-1);
        current = head;
        while list_1 and list_2:
            if list_1.val < list_2.val:
                current.next = list_1;
                list_1 = list_1.next;
            else:
                current.next = list_2;
                list_2 = list_2.next;
            current = current.next;
        if list_1:
            current.next = list_1;
        if list_2:
            current.next = list_2;
        return head.next;

# # 使用优先队列的方式进行解答此问题
# # 什么是优先队列？ 不知道！！哈哈哈
# # 堆排序
# # 算法步骤：
# # 1、建立最大堆
# # 2、取出最大元素，并维持最大堆
# # ......
# # 直到所有元素都排完序
# class MaxHeap(object):
#     def __init__(self):
#         self.vals = [];
#         self.heap_size = 0;

#     def buildMaxHeap(self):
#         for i in xrange(len(self.vals) // 2  - 1, -1, -1):
#             self.maxHeap(i);

#     def maxHeap(self, index):
#         while index <= self.heap_size //2 - 1:
#             l = 2 * index + 1;
#             r = 2 * index + 2;
#             largest = index;
#             if l < self.heap_size and self.vals[l] > self.vals[largest]:
#                 largest = l;
#             if r < self.heap_size and self.vals[r] > self.vals[largest]:
#                 largest = r;

#             if largest == index:
#                 return;

#             temp = self.vals[index];
#             self.vals[index] = self.vals[largest];
#             self.vals[largest] = temp;


#     def sort(self, nums):
#         self.vals = nums;
#         self.heap_size = len(self.vals);
#         self.buildMaxHeap();

#         while self.heap_size > 1:
#             temp = self.vals[0];
#             self.vals[0] = self.vals[self.heap_size - 1];
#             self.vals[self.heap_size - 1] = temp;

#             self.heap_size -= 1;
#             self.maxHeap(0);
#         return self.vals;

# t = MaxHeap();
# print t.sort([16, 7, 3, 20, 17, 8]);

# 优先队列是建立在最小堆这种数据结构上的
# 提供了4个方法：
# 1、 插入一个元素
# 2、 返回最小元素
# 3、 返回并删除最小元素
# 4、 把关键字key对应的数值减小到val
from Queue import PriorityQueue;
class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        head = current = ListNode(-1);
        priority_queue = PriorityQueue();
        for l in lists:
            if not l:
                continue;
            priority_queue.put( (l.val, l) );
        if priority_queue.empty():
            return [];

        while not priority_queue.empty():
            val, node = priority_queue.get();
            current.next = node;
            current = current.next;
            node = node.next;
            if not node:
                continue;
            priority_queue.put( (node.val, node) );
        return head.next;


l1 = ListNode(1);
l1.next = ListNode(4);
l1.next.next = ListNode(5);
l2 = ListNode(1);
l2.next = ListNode(3);
l2.next.next = ListNode(4);
l3 = ListNode(2);
l3.next = ListNode(6);
lists = [l1, l2, l3];

t = Solution();
printList(t.mergeKLists(lists));
